

/**
 * @作者 zxy
 * @时间 2023-03-31 13:42
 * @说明 1028. 从先序遍历还原二叉树
 * 我们从二叉树的根节点 root 开始进行深度优先搜索。
 * 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
 * 如果节点只有一个子节点，那么保证该子节点为左子节点。
 * 给出遍历输出 S，还原树并返回其根节点 root。
 * 输入："1-2--3--4-5--6--7"
 * 输出：[1,2,5,3,4,6,7]
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode treeNode = recoverFromPreorder("1-2--3--4-5--6--7");
        System.out.println(treeNode);
    }

    static String traversal;

    /**
     * 执行用时：8 ms, 在所有 Java 提交中击败了25.86%的用户
     * 内存消耗：42.2 MB, 在所有 Java 提交中击败了16.81% 的用户
     * @param traversal
     * @return
     */
    public static TreeNode recoverFromPreorder(String traversal) {
        int depth = 0;
        int value = 0;
        int valueLen = 0;
        for (int i = 0; i < traversal.length(); i++) {
            if ('-' != traversal.charAt(i)) {
                int left = i;
                while (i < traversal.length() && traversal.charAt(i) != '-') {
                    i++;
                }
                value = Integer.parseInt(traversal.substring(left, i));
                valueLen = traversal.substring(left, i).length();
                break;
            }
        }
        if (depth == 0) return null;
        TreeNode root = new TreeNode(value);
        Solution.traversal = traversal.substring(depth + valueLen);
        createTree(0, root);
        return root;
    }

    public static void createTree(int lastDepth, TreeNode node) {
        int depth = 0;
        int value = 0;
        int valueLen = 0;
        for (int i = 0; i < traversal.length(); i++) {
            if ('-' == traversal.charAt(i)) depth++;
            else {
                int left = i;
                while (i < traversal.length() && traversal.charAt(i) != '-') {
                    i++;
                }
                value = Integer.parseInt(traversal.substring(left, i));
                valueLen = traversal.substring(left, i).length();
                break;
            }
        }
        if (depth == 0 || depth <= lastDepth) return;
        node.left = new TreeNode(value);
        traversal = traversal.substring(depth + valueLen);
        createTree(depth, node.left);

        depth = 0;
        value = 0;
        for (int i = 0; i < traversal.length(); i++) {
            if ('-' == traversal.charAt(i)) depth++;
            else {
                int left = i;
                while (i < traversal.length() && traversal.charAt(i) != '-') {
                    i++;
                }
                value = Integer.parseInt(traversal.substring(left, i));
                valueLen = traversal.substring(left, i).length();
                break;
            }
        }
        if (depth == 0 || depth <= lastDepth) return;
        node.right = new TreeNode(value);
        traversal = traversal.substring(depth + valueLen);
        createTree(depth, node.right);
    }
}
